1. Field of the Invention
The present invention relates to an echo canceller with a short processing delay and a decreased number of multiplications.
It is well known that the frequency domain adaptive filter (FDAF) is superior to the time domain adaptive, filter (TDAF) concerning the of computations required. This is more realizable when the filter length is increased, as in the case of the acoustic noise or acoustic echo cancelling in speech communication systems having a long impulse response. The reduction in the computation number is obtained by replacing the convolution in the time domain by multiplication in the frequency domain, using a fast Fourier transform (FFT).
However, to realize a linear convolution of the time domain in the frequency domain, circular convolution must be considered which requires that the FFT use overlapped-save method and a block LMS algorithm. If the length of the block data introduced each time to the system is long, then the input-output, system propagation delay will also be long. If the length of the shifted data is short, then the propagation delay will be short but the multiplication number will be increased. Note, in the FDAF, the FFT length will be too long when the acoustic impulse response is too long. The impulse response of an acoustic echo path is about several hundred millisconds.
Accordingly, for the above reasons, a new echo canceller having a decreased computation number and a short propagation delay is required.
2. Description of the Related Art
The prior art will be explained with reference to FIGS. 9-14.
An echo canceller in the time domain is, as is well known and as shown in FIG. 9, constructed by a digital filter having a finite impulse response (FIR) type having coefficients h.sub.k which are the estimated values of an impulse response h.sub.k of an echo path to be estimated, where k=0, 1, . . . N-1, and N is the length of the FIR digital filter.
Each coefficient h.sub.k is obtained by an adaptive control in which the difference signal e(n) between an echo signal y(n) passed through the echo path to be estimated and the estimated output y(n) of the FIR filter is adaptively controlled to be zero. Known adaptive controls are, a successive adaptive control method and a block adaptive control method. In the successive adaptive control method, the coefficients h.sub.k are adaptively updated upon each input of one sample of the input data x(n). In the block adaptive control method, the coefficients are not updated until L samples of the input data have been input, so that the coefficients are updated as a lump at one time when L samples of input data have been received.
In the successive adaptive control method, the necessary multiplication number for each input sample is 2N. That is, N multiplications are necessary for calculating the output signal y(n), and N multiplications are necessary for updating the coefficients, resulting in the need for 2N multiplications.
In the block adaptive control method, a fast Fourier transform (FFT) is introduced to effect the processing shown in FIG. 9 in the frequency domain, so that the necessary number of multiplications can be reduced. The FFT by the block adaptive control is well known and is described in, for example, "Fast Implementation of LMS Adaptive Filters" IEEE TRANSACTION ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING, VOL. ASSP-28, No. 4 AUGUST 1980.
The basic concept thereof is as follows. The convolution expressed by: ##EQU1## can be considered, as shown in FIGS. 10B-10E, as a sum of products of the input signal x(n) (FIG. 10A) and the respective coefficients, where the coefficient series is shifted by one sample for each input signal x(n). In the figure, N represents the length of the impulse response. Until L samples after one updating , the coefficients are not updated by the adaptive control.
Now, consider a series of the input samples x(n) with a periodic period (N+L-1), each period including (N+L-1) samples x(n-N+1) through x(n+L-1) of the input data x(n), as shown in FIG. 11A. On the other hand, with respect to the coefficients h.sub.k, a series with a periodic period (N+L-1) is obtained by inserting (L-1) "1"s between the coefficients h.sub.0 and h.sub.N-1. Then, by shifting the coefficients series one sample by one sample, as shown in FIGS. 11B-11F, (N+L-1).series are obtained. Each sample of the input data x(n-N+1) through x(n+L-1) is multiplied to each of the (N+L-1) series of the coefficients shown in FIGS. 11B-11F. Then, the multiplied results are summed to obtain an output series z(n) having a period of (N+L-1). As is apparent from FIGS. 10A-10E and 11A-11F, the latter half L samples of the series z(n) is equal to the series y(n).
In another aspect, the well known cyclic convolution shown in FIGS. 11A-11F is such that the discrete Fourier transform (DFT) of the output is expressed by the products of the DFT of each input. Therefore, the above-mentioned expression (1) can be realized by a constitution shown in FIG. 12.
Referring to FIG. 12, ##EQU2## can be written.
That is, an L sample overlap part 121 receives (N-1) samples of one block of input data x(n) and L samples of the previous block of input data, to generate (N+L-1) samples of overlapped elements in which L samples of the input data are overlapped. An (N+L-1)-point FFT 122 effects a fast Fourier transform on the (N+L-1) samples with the overlapped L elements to generate (N+L-1) elements of X.sub.0 (k), X.sub.1 (k), X.sub.(N-1) (k), X.sub.N (k), . . . , X.sub.(N+L-2) (k). To the outputs X.sub.0 (k), X.sub.1 (k), . . . , estimated cofficients H.sub.k.sup.0, H.sub.k.sup.1, . . . , H.sub.k.sup.N+L-2 are respectively multiplied, where the estimated coefficients are updated once after introducing each block of data, as described later in more detail. The results of the multiplications are then subject to inverse fast Fourier transform (IFFT) in the (N+L-1)-point IFFT 123. The output y(n) is obtained at the outputs of an output processing part 124, by considering only the last half L elements of the outputs of the (N+L-1)-point IFFT 123, or by discarding the first (N-1) elements of the outputs of the IFFT 123. The error signal e(n) is obtained by subtracting the estimated output from the echo signal y(n) transmitted via the echo path. The adaptive control is effected so as to reduce the error signal e(n) to zero.
The update control of the coefficients H.sub.k.sup.i is as follows.
The equation for the update control of the coefficients is expressed as: ##EQU3##
The calculation of the second term in the right hand side of the above equation is effected, as shown in FIGS. 13A-13F, as follows. That is, consider a series of the input data x(n) with a period (N+L-1), and consider a series with (N+L-1) period including L samples of error data e(n), e(n+1), . . . , e(n+L-1) and (N-1) "0"s padded. Each element of the input data series x(n-N+1), . . . , x(n+L-1) is multiplied to the series including the error data and the "0"s.
The series with the (N+L-1) period including error data and "0"s is shifted one element by one element in response to an input data sample so that (N+L-1) series are obtained as..shown in FIGS. 13B-13F. Then, each element of the input data series in the (N+L-1) period is multiplied with each of the (N+L-1) series shown in FIGS. 13B-13F, and the sum of the products is obtained from this sum, the preceding N samples are output as the second term of the right-hand side, of the equation (3).
A theory is known in which a periodic correlation function is obtained by the product of the DFT of one input and the complex conjugate of the DFT of the other input (see, for example, "Theory and Application of Digital Signal Processing" written by R. Rabiner and B. Gold, published in 1975 by PRENTICE-HALL Inc., N.J., pg. 403).
FIG. 14 is a block diagram of a conventional echo canceller using the block LMS algorithms and including the updating portion of the coefficients utilizing the above mentioned theory. In FIG. 14, 140 is an overlap processing part; 141 is an (N+L-1)-point FFT; 142 is a complex multiplication part; 143 is an (N+L-1) point inverse FFT; 144 is an output processing part for outputting the last L samples; 145 is a zero padding part; 146 is an (N+L-1) point FFT, 147 is a complex multiplication part; 148 is an IFFT; and 149 is an FFT.
Assuming that the response length is N, then the overlap processing part 140 receives an input signal x(n) and makes (N+L-1) samples as one block. Then, by overlapping L samples of one block and the successive block, the overlap processing part 140 outputs (N+L-1) samples of the input data x(n).
The (N+L-1) point FFT 141 receives each block of the input data x(n) to carry out a Fourier transform on each received block so that the input data x(n), which is represented in the time domain, is transformed to the signals X.sub.0 (k), X.sub.1 (k), . . . X(N+L-2)(k), which are represented in the frequency domain. In the complex multiplication part 142, the coefficients H.sub.k.sup.0, H.sub.k.sup.1, . . . , H.sub.k.sup.N+L-2 are respectively multiplied to the signals X.sub.0 (k), X.sub.1 (k), . . . , X(N+L-2) in the frequency domain. The (N+L-1) point IFFT 143 receives the results of the multiplications and transforms the signals from the frequency domain representation to the time domain representation.
The output processing part 144 receives the (N+L-1) samples of the time domain representation and outputs the last L samples thereof. The output signal y(n) is subtracted from the echo signal y(n), which has passed through the acoustic echo path, resulting in an error signal e(n).
The error signal e(n) has L samples. In the zero padding part 145, (N-1) "0"s are padded in the portion preceiding the L samples of the error signal e(n). The (N+L-1) point FFT 146 receives the (N+L-1) samples of the "0"s and error signal e(n) to transform them into signal D.sub.k.sup.0, K.sub.k.sup.1, . . . , D.sub.k.sup.(N+L-2) in the frequency domain.
At the complex multiplication part 147, the signals E.sub.k.sup.0, E.sub.k.sup.1, . . . , E.sub.k.sup.(N+L-2) and the complex conjugatesof the signals X.sub.0 (k), X.sub.1 (k), X.sub.(N+L-2) k are respectively multiplied. The multiplied results are applied to the IFFT 148 so that the signals are transformed from the frequency domain representation to the time domain representation. The preceiding N samples of the output of the IFFT 148 are supplied to the FFT 149. In addition, the FFT 149 receives (L-1) samples of "0"s as the last (L-1) samples of the input signal. Thus, at the output of the IFFT 149, updating parts of the tap coefficients H.sub.k.sup.0, H.sub.k.sup.1, . . . , H.sub.k.sup.(N+L-2 are obtained. The tap coefficients are once obtained are updated, or in other words refreshed, after introducing each block of the input data x(n).
The refreshing of the tap copefficients is further described. The tap coefficients are updated at ach input of one block. Assuming that the L samples constitute one adaption block, and assuming that k is an integer, then, as the coefficient values in the period between kL and {KL+(L-1)}, the values of which were updated at the time KL, are used. The next coefficient values at the next time (K+1) are determined in such a way that the sum of the squares of the errors during the period between KL and {KL+(L-1)} is made minimum. In this case, assuming that the evaluation number is D, then, EQU D=e.sub.KL.sup.2 +e.sub.KL+1.sup.2 + . . . +e.sub.KL+(L-1).sup.2( 4) can be obtained.
The error e.sub.KL+1 can be expressed as: ##EQU4## where h.sup.i represents an impulse response of the actual system; h.sub.KL.sup.i represents an estimated impulse response; and X.sub.KL+l-i represents a sample of the series of the input data. Whereas, the following equation stands. ##EQU5## Therefore, the updating of the coefficients is expressed by ##EQU6## where .mu. is a constant value. Expression of the equation (7) in the vector form is as follows: ##EQU7## In the algorithm utilizing an FFT, assume that: ##EQU8## Then, the output vector Y.sub.K.sup.T is obtained by the latter half L samples of the cyclic convolution with a periodic period equal to (N+L-1) of the vectors H.sub.K.sup.T and X.sub.K.sup.T expressed by the equations (10) and (11). The FFT of the output of the cyclic convolution is the products of the FFT of each element which is subject to convolution. Therefore, the fundamental structure of the echo canceller shown in FIG. 14 is constructed by the parts 140-144. The coefficients H.sub.K.sup.0 -H.sub.K.sup.(N+L-2) are updated by the outputs of the FFT 149. To update the coefficients, (L-1) zeros are padded in the FFT 149 to the second term in the equation (8), which is thus changed as follows. ##EQU9##
It is known that the IFFT 148 and the FFT updating the coefficients can be omitted (see "Unconstrained Frequency-Domain Adaptive Filter" D. Mansour et al., IEEE vol ASSP-30, No. 5, October 1982).
In the construction shown in FIG. 14, the necessary number of multiplications for each input of one sample is expressed as follows: ##EQU10## where (N+L-1) is assumed to be an n-th power of 2. By the equation proposed by Mansour et al., this is expressed as: ##EQU11## On the other hand, by a usual adaptive control effected sample by sample in the time domain, the necessary number of multiplications is as large as 2N.
When L and N are nearly equal in order of magnitude, the value expressed by the equation (14) or (15) is small in comparison with the number 2N.
However, in an echo canceller for an acoustic system, the length of the impulse response is so long that the number N becomes several thousand or more. Whereas, the block length L should be as small as possible, because it provides, as it is, a processing delay, and in order to minimize the influence due to fluctuation of the system. If L is sufficiently small in comparison with N, the value expressed by the equation (14) or (15) becomes almost equal to or larger than 2N.
Also, if (N+L-1) is not an n-th power of 2, the echo canceller having the structure shown in FIG. 14 cannot operate effectively. For example, assume that N=4096 and L=50, then the FFT portion shown in FIG. 14 must be arranged to execute 8096 multiplications resulting in an increase in the processing delay.